// tspcluster - Traveling Salesman Problem
// Copyright (C) 2006  Frederik Carlier
//
// This library is free software; you can redistribute it and/or
// modify it under the terms of the GNU Lesser General Public
// License as published by the Free Software Foundation; either
// version 2.1 of the License, or (at your option) any later version.
//
// This library is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
// Lesser General Public License for more details.
//
// You should have received a copy of the GNU Lesser General Public
// License along with this library; if not, write to the Free Software
// Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301  USA

using System;
using System.Collections.Generic;
using System.Text;
using System.Diagnostics;

namespace UGent.Tsp
{
    /// <summary>
    /// Inverts k random cities.
    /// </summary>
    [HasParameter(true,2)]
    class Swap361 : ISwapper
    {
        private const int DefaultCount = 35;

        #region Constructors
        public Swap361(Route route)
            : this(route, DefaultCount)
        {
        }

        public Swap361(Route route, int count)
        {
            this.route = route;
            this.cityCount = route.Map.CityCount;
            this.count = count;
            this.cities = new int[count];
            this.subset = new Subset();
        }
        #endregion

        #region Properties
        // The set of cities that specify the subroute to be inversed
        private int[] cities;
        private int this[int index]
        {
            get
            {
                return cities[Cyclic.GetIndex(index, count)];
            }
            set
            {
                cities[Cyclic.GetIndex(index, count)] = value;
            }
        }
        private int cityCount;
        private int proposed;
        private int accepted;
        private Subset subset;

        public int ProposedMoves
        {
            get { return proposed; }
        }

        public int AcceptedMoves
        {
            get { return accepted; }
        }

        private Route route;
        public IRoute Route
        {
            get { return route; }
        }

        private int count;
        public int Count
        {
            get
            {
                return count;
            }
        }
        #endregion

        #region ISwapper Members

        public void Generate()
        {
            // Generate a set of k unique random
            // numbers from a set of N values
            // (eg: get k unique numbers from 0..N-1)
            subset.Random(0, cityCount - 1, count, cities);
            proposed++;
        }

        public void Do()
        {
            int temp, upper, city, partner;

            if (count % 2 == 0)
                upper = count / 2 - 1;
            else
                upper = (count - 1) / 2;

            for (int i = 0; i <= upper; i++)
            {
                city = cities[i];
                partner = cities[count - 1 - i];

                temp = route[city];
                route[city] = route[partner];
                route[partner] = temp;
            }

            accepted++;
        }

        public double GetDelta()
        {
            double delta = 0;

            for (int i = 0; i < count; i++)
            {
                int oldIndex = this[i];
                int oldLeft = Cyclic.GetIndex(oldIndex - 1, cityCount);
                int oldRight = Cyclic.GetIndex(oldIndex + 1, cityCount);
                int newIndex = this[count - 1 - i];
                int newLeft = -1;
                int newRight = -1;

                // Is the city at the left at the new position a shifted city?
                // The next city to be shifted will be the shifted city closest to
                // the left.
                bool newLeftHasShifted = (this[count - 1 - (i + 1)] == Cyclic.GetIndex(newIndex - 1, cityCount));

                if (newLeftHasShifted)
                {
                    // If so, the new left city is the city that 
                    // will be moved next.
                    newLeft = this[i + 1];
                }
                else
                {
                    // If not, it is the city at the left of the new location.
                    newLeft = Cyclic.GetIndex(newIndex - 1, cityCount);
                }

                // Is the city at the right at the new position a shifted city?
                // The previous city to be shifted will be the shifted city closest to
                // the right.
                bool newRightHasShifted = (this[count - 1 - (i - 1)] == Cyclic.GetIndex(newIndex + 1, cityCount));

                if (newRightHasShifted)
                {
                    // If so, the new left city is the city that 
                    // was moved previously.
                    newRight = this[i - 1];
                }
                else
                {
                    // If not, the new right is the city right of the
                    // new location.
                    newRight = Cyclic.GetIndex(newIndex + 1, cityCount);
                }

                // Debug.WriteLine(String.Format("City with index {0} had the old configuration {1}-{0}-{2}, and has the new configuration {3}-{0}-{4}", oldIndex, oldLeft, oldRight, newLeft, newRight));

                delta -= Route.GetDistance(oldLeft, oldIndex);
                //Debug.WriteLine(string.Format("-d({0},{1})", oldLeft, oldIndex));

                delta += Route.GetDistance(newLeft, oldIndex);
                //Debug.WriteLine(string.Format("+d({0},{1})", newLeft, oldIndex));

                if (!newRightHasShifted)
                {
                    delta += Route.GetDistance(oldIndex, newRight);
                    //Debug.WriteLine(string.Format("+d({0},{1})", oldIndex, newRight));
                }

                bool oldRightHasShifted = Cyclic.GetIndex(this[i] + 1, cityCount) == this[i + 1];
                if (!oldRightHasShifted)
                {
                    delta -= Route.GetDistance(oldIndex, oldRight);
                    //Debug.WriteLine(string.Format("-d({0},{1})", oldIndex, oldRight));
                }
            }

            //Debug.WriteLine(string.Empty);
            return delta;
        }

        #endregion
    }
}
